package org.example.myleet.p779;

public class Solution {
    public int kthGrammar(int n, int k) {
        int reverseCount = 0;
        int len = 1 << (n - 1);
        int halfLen;
        while (len > 1) {
            halfLen = len >> 1;
            if (k > halfLen) {
                k -= halfLen;
                ++reverseCount;
            }
            len = halfLen;
        }
        return (reverseCount & 1) == 1 ? 1 : 0;
    }
}
